package example4;

import java.util.Arrays;

//322. 零钱兑换
public class LeetCode322 {
    public static void main(String[] args) {
        int[] coins = {1,2,5};
        System.out.println(new Solution322_2().coinChange(coins,11));
    }
}

/**
 * 方法二：动态规划，其实就是方法一递归的反过来，只不过方法一是从amount往0开始找，
 * 这个动态规划是从0往amount开始找，状态转移方程还是一样的dp[amount] = min(dp[amount - dp[j]]) + 1
 */
class Solution322_2 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for(int i=1;i<=amount;i++){
            int min = 10000;
            for(int j=0;j<coins.length;j++){
                if(i - coins[j] < 0 || dp[i-coins[j]] == -1)    continue;
                if(min > dp[i-coins[j]]) min = dp[i-coins[j]];
            }
            if(min == 10000){
                dp[i] = -1;
            }else{
                dp[i] = min + 1;
            }
        }
        return dp[amount];
    }
}

/**
 * 方法一：递归
 * 定义一个结果数组dp[]，用于存储金额为i的最少用到的硬币数量，本题要求amount的最小数量，
 * 那么就定义dp = new int[amount]，dp[amount-1]就是凑到amount所需要的最少的数量，
 * 那么可以依次遍历coins数组，求得dp[amount - coins[i]]的最小值，那么dp[amount-1]就等于
 * 这个最小值 + 1，要求dp[amount-coins[i]]那么还是上面一样的操作，递归就行，划定好递归退出的界限。
 */
class Solution322_1 {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        int[] dp = new int[amount];
        return fun(coins,amount,dp);
    }

    public int fun(int[] coins,int amount,int[] dp){
        if(amount < 0)  return -1;
        if(amount == 0) return 0;
        int min = 10000;
        if(dp[amount-1] != 0){
            return dp[amount-1];
        }
        for(int i=0;i<coins.length;i++){
            int temp = fun(coins, amount - coins[i],dp);
            if(temp >= 0 && min > temp)  min = temp;
        }
        dp[amount-1] = min == 10000 ? -1 : min + 1;
        return dp[amount-1];
    }
}
